package com.mlh.dp.编辑距离;

/**
 * @author 缪林辉
 * @date 2024/5/21 14:20
 * @DESCRIPTION
 */
// 给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
// 字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
// 进阶：
// 如果有大量输入的 S，称作 S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？
public class 判断子序列 {
    //该方法没有用动态规划，利用双指针
    public boolean method1(String s, String t) {
        char[] sc = s.toCharArray();
        char[] tc = t.toCharArray();
        int sindex=0;
        int tindex=0;
        while (tindex<tc.length&&sindex<sc.length){
            if(tc[tindex]==sc[sindex]){
                tindex++;
                sindex++;
            }else{
                tindex++;
            }
        }
        if(sindex==sc.length){
            return true;
        }
        return false;
    }

    //动态规划的话直接用最长公共子序列的代码来做就行
    public boolean method2(String s, String t) {
        char[] sc = s.toCharArray();
        char[] tc = t.toCharArray();
        int[][] dp=new int[sc.length+1][tc.length+1];
        for (int i = 1; i <=sc.length; i++) {
            for (int j = 1; j <=tc.length ; j++) {
                if(sc[i-1]==tc[j-1]){
                    dp[i][j]=dp[i-1][j-1]+1;
                }else{
                    dp[i][j]=Math.max(dp[i][j-1],dp[i-1][j]);
                }
            }
        }
        //在这里加个判断即可，最终最长公共子序列长度=s字符串的长度，就满足题目要求返回true，否则返回false
        if(dp[sc.length][tc.length] == sc.length){
            return true;
        }else{
            return false;
        }
    }
}
